{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Merge Nodes in Between Zeros"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #linked-list #simulation"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #链表 #模拟"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: mergeNodes"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #合并零之间的节点"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个链表的头节点 <code>head</code> ，该链表包含由 <code>0</code> 分隔开的一连串整数。链表的 <strong>开端</strong> 和 <strong>末尾</strong> 的节点都满足 <code>Node.val == 0</code> 。</p>\n",
    "\n",
    "<p>对于每两个相邻的 <code>0</code> ，请你将它们之间的所有节点合并成一个节点，其值是所有已合并节点的值之和。然后将所有 <code>0</code> 移除，修改后的链表不应该含有任何 <code>0</code> 。</p>\n",
    "\n",
    "<p>&nbsp;返回修改后链表的头节点 <code>head</code> 。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：<br />\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2022/02/02/ex1-1.png\" style=\"width: 600px; height: 41px;\" /></strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>head = [0,3,1,0,4,5,2,0]\n",
    "<strong>输出：</strong>[4,11]\n",
    "<strong>解释：</strong>\n",
    "上图表示输入的链表。修改后的链表包含：\n",
    "- 标记为绿色的节点之和：3 + 1 = 4\n",
    "- 标记为红色的节点之和：4 + 5 + 2 = 11\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：<br />\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2022/02/02/ex2-1.png\" style=\"width: 600px; height: 41px;\" /></strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>head = [0,1,0,3,0,2,2,0]\n",
    "<strong>输出：</strong>[1,3,4]\n",
    "<strong>解释：</strong>\n",
    "上图表示输入的链表。修改后的链表包含：\n",
    "- 标记为绿色的节点之和：1 = 1\n",
    "- 标记为红色的节点之和：3 = 3\n",
    "- 标记为黄色的节点之和：2 + 2 = 4\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li>列表中的节点数目在范围 <code>[3, 2 * 10<sup>5</sup>]</code> 内</li>\n",
    "\t<li><code>0 &lt;= Node.val &lt;= 1000</code></li>\n",
    "\t<li><strong>不</strong> 存在连续两个&nbsp;<code>Node.val == 0</code> 的节点</li>\n",
    "\t<li>链表的 <strong>开端</strong> 和 <strong>末尾</strong> 节点都满足 <code>Node.val == 0</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [merge-nodes-in-between-zeros](https://leetcode.cn/problems/merge-nodes-in-between-zeros/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [merge-nodes-in-between-zeros](https://leetcode.cn/problems/merge-nodes-in-between-zeros/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[0,3,1,0,4,5,2,0]', '[0,1,0,3,0,2,2,0]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def mergeNodes(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        pre_num = 0\n",
    "        i = head\n",
    "        j = head.next\n",
    "        while j:\n",
    "            pre_num = 0\n",
    "            while j.val != 0:\n",
    "                pre_num += j.val\n",
    "                j = j.next\n",
    "            i.next = j\n",
    "            i, i.val= j, pre_num\n",
    "            j = j.next\n",
    "        return head.next\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def mergeNodes(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        dummy = ListNode(-1)\n",
    "        dummy.next = head\n",
    "        slow = dummy\n",
    "        fast = dummy.next\n",
    "\n",
    "        pre = 0\n",
    "        while fast:\n",
    "            if fast.val == 0:\n",
    "                if pre:\n",
    "                    slow.next.val = pre\n",
    "                    slow = slow.next\n",
    "                pre = 0\n",
    "            else:\n",
    "                pre += fast.val\n",
    "            fast = fast.next\n",
    "        \n",
    "        if pre:\n",
    "            slow.next.val = pre\n",
    "            slow = slow.next\n",
    "        slow.next = None\n",
    "        return dummy.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def mergeNodes(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        cur = head\n",
    "        dummy = ListNode(0)\n",
    "        tmp = dummy\n",
    "        while cur:\n",
    "            nex = cur.next\n",
    "            sum1 = 0\n",
    "            while nex and nex.val != 0:\n",
    "                sum1 += nex.val\n",
    "                nex = nex.next\n",
    "            if sum1 != 0:\n",
    "                tmp.next = ListNode(sum1)\n",
    "                tmp = tmp.next\n",
    "            #print(tmp)\n",
    "            cur.next = nex\n",
    "            cur = cur.next\n",
    "        return dummy.next\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def mergeNodes(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        nodelst = []\n",
    "        vallst=[]\n",
    "        th = head\n",
    "        while(th):\n",
    "            nodelst.append(th)\n",
    "            vallst.append(th.val)\n",
    "            th=th.next\n",
    "        tval  = 0\n",
    "        th = head \n",
    "        for i in range(1,len(nodelst)):\n",
    "            tval+=vallst[i]\n",
    "            if vallst[i]==0:\n",
    "                temp = ListNode(tval)\n",
    "                head.next = temp\n",
    "                head= head.next\n",
    "                #head.next = nodelst[i]\n",
    "                #head=head.next\n",
    "\n",
    "                tval = 0\n",
    "        return th.next\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def mergeNodes(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        dummy = ListNode(next=head)\n",
    "        left = dummy\n",
    "        pre, cur = head, head.next\n",
    "        while cur:\n",
    "            tmp = 0\n",
    "            while cur and cur.val != 0:\n",
    "                tmp += cur.val\n",
    "                pre = cur\n",
    "                cur = cur.next\n",
    "            if not cur:\n",
    "                break\n",
    "            cur.val = tmp\n",
    "            tmp = 0\n",
    "            left.next, left, pre, cur = cur, cur, cur, cur.next\n",
    "        return dummy.next\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "\n",
    "class Solution:\n",
    "    def mergeNodes(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        res = ans = ListNode()\n",
    "        head = head.next\n",
    "        temp = 0\n",
    "        while head:\n",
    "            if head.val != 0:\n",
    "                temp += head.val\n",
    "            else:\n",
    "                ans.next = head\n",
    "                ans = ans.next\n",
    "                ans.val = temp\n",
    "                temp = 0\n",
    "                ans.next = head.next\n",
    "\n",
    "            head = head.next\n",
    "        return res.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def mergeNodes(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        Node = ListNode()\n",
    "        \n",
    "        sum = Node\n",
    "        \n",
    "        bb = 0\n",
    "        while head.next!=None:\n",
    "            if head.next.val!=0:\n",
    "                bb += head.next.val\n",
    "                head = head.next\n",
    "                \n",
    "            else:\n",
    "                Node.next = ListNode(val=bb)\n",
    "\n",
    "                Node = Node.next\n",
    "               \n",
    "                bb = 0                \n",
    "                head.next = head.next.next\n",
    "    \n",
    "        return sum.next\n",
    "        \n",
    "\n",
    "\n",
    "\n",
    "                \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def mergeNodes(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        dummy = cur = ListNode(-1)\n",
    "        v = 0\n",
    "        head = head.next\n",
    "        while head:\n",
    "            v += head.val\n",
    "            if head.val == 0:\n",
    "                head.val = v\n",
    "                cur.next = head \n",
    "                cur = cur.next\n",
    "                v = 0\n",
    "            head = head.next\n",
    "        return dummy.next\n",
    "            \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def mergeNodes(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        dummy = ListNode()\n",
    "        pointer = dummy\n",
    "        while head is not None:\n",
    "            if head.val == 0:\n",
    "                head = head.next\n",
    "                while head is not None and head.next.val != 0:\n",
    "                    head.next.val += head.val\n",
    "                    head = head.next\n",
    "                pointer.next = head\n",
    "                pointer = pointer.next\n",
    "            if head is not None:    \n",
    "                head = head.next\n",
    "\n",
    "\n",
    "        return dummy.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def mergeNodes(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        arr=[]\n",
    "        i=head\n",
    "        while i.next:\n",
    "            if i.next.val!=0:\n",
    "                i.next.val+=i.val\n",
    "            else:\n",
    "                arr.append(i.val)\n",
    "            i=i.next\n",
    "        head=ListNode(arr[0])\n",
    "        temp=head\n",
    "        for i in range(1,len(arr)):\n",
    "            node=ListNode(arr[i])\n",
    "            temp.next=node\n",
    "            temp=node\n",
    "        return head\n",
    "\n",
    "\n",
    "            \n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def mergeNodes(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        cur = head\n",
    "        dcur = head.next\n",
    "        sum_val = 0\n",
    "        while dcur != None:\n",
    "            if dcur.val != 0:\n",
    "                sum_val += dcur.val\n",
    "            if dcur.val == 0:\n",
    "                cur.next = ListNode(sum_val,dcur)\n",
    "                cur = dcur\n",
    "                sum_val = 0\n",
    "            dcur = dcur.next\n",
    "\n",
    "        flag  = 0\n",
    "        cur = head\n",
    "        while cur != None:\n",
    "            if cur.val != 0 and flag == 1:\n",
    "                new_head.next = ListNode(cur.val)    \n",
    "                new_head = new_head.next\n",
    "            if cur.val != 0 and flag == 0:\n",
    "                new_head = ListNode(cur.val)\n",
    "                return_head = new_head\n",
    "                flag = 1\n",
    "                \n",
    "\n",
    "            cur = cur.next\n",
    "        \n",
    "        return return_head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def mergeNodes(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        virtualhead=ListNode(next=head)\n",
    "        pre=virtualhead\n",
    "        cur=head\n",
    "        while cur:\n",
    "            count=0\n",
    "            while  cur and cur.val!=0:\n",
    "                count+=cur.val\n",
    "                cur=cur.next\n",
    "            if cur and cur.val==0:\n",
    "                node=ListNode(val=count)\n",
    "                pre.next=node\n",
    "                pre=node\n",
    "                cur=cur.next\n",
    "        return virtualhead.next.next\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def mergeNodes(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        start = head.next\n",
    "        nodelist = []; value = 0\n",
    "        while(start != None):\n",
    "            if start.val == 0:\n",
    "                nodelist.append(value)\n",
    "                value = 0\n",
    "            else:\n",
    "                value += start.val\n",
    "            start = start.next\n",
    "        answer = ListNode(nodelist[0], None)\n",
    "        pointer = answer\n",
    "        for count in nodelist[1:]:\n",
    "            pointer.next = ListNode(count, None)\n",
    "            pointer = pointer.next\n",
    "        return answer\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def mergeNodes(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        dummy = tail = ListNode()\n",
    "        total = 0\n",
    "        cur = head.next\n",
    "\n",
    "        while cur:\n",
    "            if cur.val == 0:\n",
    "                node = ListNode(total)\n",
    "                tail.next = node\n",
    "                tail = tail.next\n",
    "                total = 0\n",
    "            else:\n",
    "                total += cur.val\n",
    "            \n",
    "            cur = cur.next\n",
    "        \n",
    "        return dummy.next\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def mergeNodes(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        ans = ListNode()\n",
    "        tmp = ans\n",
    "        cur = 0\n",
    "        while head:\n",
    "            if head.val == 0 and cur:\n",
    "                tmp.next = ListNode(cur)\n",
    "                tmp = tmp.next\n",
    "                cur = 0\n",
    "            cur += head.val\n",
    "            head = head.next\n",
    "        return ans.next\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def mergeNodes(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        ans = ListNode(0)\n",
    "        q = ans\n",
    "        stack = []\n",
    "        cur = head\n",
    "        while head:\n",
    "            if head.val==0 and stack:\n",
    "                tmp = 0\n",
    "                while stack:\n",
    "                    tmp += stack.pop() \n",
    "                q.next = ListNode(tmp)\n",
    "                q = q.next\n",
    "            elif head!=0:\n",
    "                stack.append(head.val)\n",
    "            head = head.next\n",
    "        return ans.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def mergeNodes(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        data=[]\n",
    "        while head:\n",
    "            data.append(head.val)\n",
    "            head=head.next\n",
    "        left=0;tmp=[]\n",
    "        for i in range(1,len(data)):\n",
    "            if data[i]==0:\n",
    "                tmp.append(data[left:i])\n",
    "                left=i+1\n",
    "        tmp=[sum(x) for x in tmp]\n",
    "        ans1=ans2=ListNode(0)\n",
    "        for val in tmp:\n",
    "            ans2.next=ListNode(val)\n",
    "            ans2=ans2.next\n",
    "        return ans1.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def mergeNodes(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        count=0\n",
    "        list1=[]\n",
    "        while head and head.next:\n",
    "            while head.next.val!=0:\n",
    "                count+=head.next.val\n",
    "                head=head.next\n",
    "            list1.append(count)\n",
    "            head=head.next\n",
    "            count=0\n",
    "        list1=list1[::-1]\n",
    "    \n",
    "        head=ListNode(list1.pop())\n",
    "        node=head\n",
    "        while list1:\n",
    "            node.next=ListNode(list1.pop())\n",
    "            node=node.next\n",
    "            \n",
    "        return head\n",
    "        \n",
    "        \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def mergeNodes(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        nums = []\n",
    "        while head:\n",
    "            nums.append(head.val)\n",
    "            head = head.next\n",
    "        stk = []\n",
    "        while nums:\n",
    "            cur = nums.pop()\n",
    "            if cur == 0:\n",
    "                sum1 = 0\n",
    "                while nums and nums[-1] != 0:\n",
    "                    sum1 += nums.pop()\n",
    "                if sum1:\n",
    "                    stk.append(sum1)\n",
    "        res = ListNode(0)\n",
    "        pre = res\n",
    "        while stk:\n",
    "            pre.next = ListNode(stk.pop())\n",
    "            pre = pre.next\n",
    "        return res.next\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def mergeNodes(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        arr = []\n",
    "        d_head = ListNode(-1)\n",
    "        d_head.next = head\n",
    "        d_head = d_head.next\n",
    "        while d_head:\n",
    "            arr.append(d_head.val)\n",
    "            d_head = d_head.next\n",
    "\n",
    "        arr = list(reversed(arr))\n",
    "        print(arr)\n",
    "        r_head = ListNode(-1)\n",
    "        d_head = r_head\n",
    "        while len(arr):\n",
    "            cnt,zero_cnt = 0,0\n",
    "\n",
    "            while len(arr) and zero_cnt <= 1:\n",
    "                top_v = arr.pop()\n",
    "                cnt += top_v\n",
    "                if top_v == 0:\n",
    "                    zero_cnt += 1\n",
    "\n",
    "            d_head.next = ListNode(cnt) if cnt > 0 else None\n",
    "            if zero_cnt == 2: arr.append(0)\n",
    "\n",
    "            d_head = d_head.next\n",
    "        return r_head.next\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mergeNodes(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        res = []\n",
    "        ans = []\n",
    "        while head:   \n",
    "            res.append(head.val)\n",
    "            head = head.next\n",
    "        i = 0\n",
    "        \n",
    "        while i < len(res):\n",
    "            tmp = 0\n",
    "            if res[i] == 0:\n",
    "                j = i + 1\n",
    "                while j < len(res) and res[j] != 0:\n",
    "                    tmp += res[j]\n",
    "                    j += 1\n",
    "                if tmp != 0:\n",
    "                    ans.append(tmp)\n",
    "                i = j\n",
    "            else:\n",
    "                i += 1\n",
    "        head = ListNode()\n",
    "        cur = head\n",
    "        for i in ans:\n",
    "            cur.next = ListNode(i)\n",
    "            cur = cur.next\n",
    "        return head.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def mergeNodes(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        ret = []\n",
    "        while head:\n",
    "            ret.append(head.val)\n",
    "            head = head.next\n",
    "        cnt, left, right = 0, 0, 1\n",
    "        while right < len(ret):\n",
    "            while right < len(ret) and ret[right] != 0:\n",
    "                right += 1\n",
    "            ret[cnt] = sum(ret[left:right])\n",
    "            cnt += 1\n",
    "            left = right\n",
    "            right += 1\n",
    "        print(ret)\n",
    "        pre = ListNode(0)\n",
    "        while cnt:\n",
    "            temp = ListNode(ret[cnt-1])\n",
    "            temp.next = pre.next\n",
    "            pre.next = temp\n",
    "            cnt -= 1\n",
    "        return pre.next\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def mergeNodes(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        left, right = head, head\n",
    "        result_head = None\n",
    "        result_tail = None\n",
    "\n",
    "        while left and right and left.next is not None and right.next is not None:\n",
    "            if left.val == 0 and right.val == 0:\n",
    "                left = left.next\n",
    "                right = right.next\n",
    "\n",
    "                if result_head is None:\n",
    "                    result_tail = result_head = ListNode()\n",
    "                else:\n",
    "                    result_tail.next = ListNode()\n",
    "                    result_tail = result_tail.next\n",
    "            elif left.val != 0 and right.val != 0:\n",
    "                result_tail.val += right.val\n",
    "                right = right.next\n",
    "            elif left.val != 0 and right.val == 0:\n",
    "                left = right\n",
    "\n",
    "        return result_head if result_head.val != 0 else None\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def mergeNodes(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        ans=ListNode(0)\n",
    "        p=ans\n",
    "        x=head.next\n",
    "        c=0\n",
    "        while x:\n",
    "            if x.val==0:\n",
    "                p.next=ListNode(c)\n",
    "                p=p.next\n",
    "                c=0\n",
    "            else:\n",
    "                c+=x.val\n",
    "            x=x.next\n",
    "        return ans.next"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
